package _02_greedy_algorithm.coinchange;

import org.junit.jupiter.api.Test;

import java.util.concurrent.atomic.AtomicInteger;

/**
 * @author: mornd
 * @dateTime: 2023/7/19 - 14:58
 * 零钱兑换
 */
public class Leetcode322 {
    /**
     * 得出可以凑成总金额所需的最少的硬币个数，如果没有任何一种硬币组合能组成总金额，得到 -1
     */
    @Test
    public void test1() {
//        coinChange(0, new int[]{2, 1}, 5, new LinkedList<>(), true);
//        coinChange(0, new int[]{5, 2, 1}, 5, new LinkedList<>(), true);
//        coinChange(0, new int[]{2}, 5, new LinkedList<>(), true); // -1
//        coinChange(0, new int[]{15, 10, 1}, 21, new LinkedList<>(), true); // 3
        coinChange(0, new int[]{5, 10, 25}, 21, new AtomicInteger(-1)); // 4
        System.out.println(min);
    }

    private int min = -1;

    private void coinChange(int index, int[] coins, int amount, AtomicInteger count) {
        count.incrementAndGet();
        if (amount == 0) {
            if (min == -1) {
                min = count.get();
            } else {
                min = Integer.min(count.get(), min);
            }
        } else if (amount > 0) {
            for (int i = index; i < coins.length; i++) {
                coinChange(i, coins, amount - coins[i], count);
            }
        }

        count.decrementAndGet();
    }
}
